/*
 * Copyright (c) 2011-2012 Alexander Dubu
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * o  Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * o  Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * o  Neither the name Axil nor the names of its contributors may be used to
 *    endorse or promote products derived from this software without specific
 *    prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

package axil.stdlib.collection.type;

import axil.api.AxilObject;
import axil.api.AxilType;
import axil.framework.type.Added;
import axil.framework.type.Subtracted;
import axil.stdlib.core.type.Nil;

import java.util.Iterator;

import static axil.framework.Functions.axil;
import static axil.framework.Functions.error;


/**
 * An immutable list composed of cons cells. To a Lisp person, this will make
 * perfect sense as a list, but its just confusing to most people. So, we call
 * this a "bag" instead.
 */
public class Bag<T extends AxilObject> extends AxilCollection<T>
	implements Sequence<T>, Added, Subtracted {
	public static final AxilType type = Bag_Type.object;
	public static final Bag empty = new Bag();

	private T object;
	private Bag<T> next;
    private boolean immutable;


	public Bag() {
	}


	public Bag(T... values) {
		final int size = values.length;
		if (size == 0) {
			return;
		}
		Bag<T> cell = null;
		for (int i = size - 1; i > 0; i --) {
			cell = new Bag(cell, values[i]);
		}
		this.object = values[0];
		this.next = cell;
	}


	public Bag(T object) {
		this.object = object;
		this.next = null;
	}


	private Bag(Bag<T> next, T object) {
		this.next = next;
		this.object = object;
	}

	/**
	 * Get the type metadata for this object. The type metadata contains
	 * information about the type itself, as an object.
	 */
	public AxilType type() {
		return type;
	}


	/**
	 * Tell if this collection contains the value (not the key) given.
	 */
	public boolean has(AxilObject object) {
        if(empty()) {
            return false;
        }

        Iter<AxilObject> iter = (Iter) this.iterator();
        while (iter.hasNext()) {
            if (iter.next().equalTo(object)) {
                return true;
            }
        }
        return false;
    }


	/**
	 * Tell if this object is equivalent to the given object. The object given
	 * is never null. The object given may be of any type of value object.  If
	 * the given object is not a suitable type for comparison, a
	 * ClassCastException may be thrown.
	 */
	public boolean equalTo(AxilObject object) {
		if (! (object instanceof AxilCollection)) {
			return false;
		}
        if (size() != ((AxilCollection) object).size()) {
            return false;
        }
		Iterator ti = this.iterator();
		while(ti.hasNext()) {
			if (! ((AxilCollection) object).has((AxilObject) ti.next())) {
                return false;
            }
		}
		return true;
	}


	public Bag<T> put(T value) {
        edit();
		return empty() ? new Bag(value) : new Bag(this, value);
	}

    public Bag<T> put(AxilCollection<T> collection) {
        edit();
        Bag<T> newHead = cloned();
        Iterator iter = collection.iterator();
        while (iter.hasNext()) {
            Bag<T> newBag = new Bag((AxilObject) iter.next());
            newBag.next = newHead.next;
            newHead.next = newBag;
        }
        return newHead;
    }


	/**
	 * Get the first element from this sequential collection, or return null
	 * if this collection is empty.
	 */
	public T first() {
		return this.object;
	}


	/**
	 * Get the last element from this sequential collection, or return null if
	 * this collection is empty.
	 */
	public T last() {
		Bag<T> cell = this;
		while(true) {
			if (cell.next == null) {
				return cell.object;
			}
			cell = cell.next;
		}
	}

    /**
     * Get all of the values in this bag and return
     */


	/**
	 * Get the element at the given index, where the first object is at index
	 * zero. If there is no element at that position, then a null is returned.
	 */
	public T at(int index) {
		Bag<T> cell = this;
		int i = 0;
		while(true) {
			if (i == index) {
				return cell.object;
			}
			cell = cell.next;
			if (cell == null) {
				return null;
			}
		}
	}


	/**
	 * Return a list containing all of the elements except the first element.
	 * This method is constant time and does not alter this object. A null is
	 * returned if this list is empty or only contains one element.
	 */
	public Bag<T> rest() {
		return next;
	}


	/**
	 * Add the given value to this value, returning a new object. The given
	 * value is never null or nil. The value may be a numeric type of any other
	 * type of object that can sensibly implement the Added interface.
	 */
	public AxilObject add(AxilObject object) {
        if (object == Nil.object) {
            return Nil.object;
        }
        Bag<T> a = immutable ? cloned() : this;
        if (object instanceof AxilCollection) {
            return a.put((AxilCollection) object).immute();
        } else {
            return a.put((T)object).immute();
        }
	}


	/**
	 * Subtract the given object from this object. The given value is never
	 * null or nil. The value may be a numeric type of any other type of object
	 * that can sensibly implement the Subtracted interface.
	 */
	public AxilObject subtract(AxilObject n) {
        if (n == Nil.object) {
            return Nil.object;
        }
        if (n instanceof AxilCollection) {
            Bag<T> newBag = immutable ? cloned() : this;
            for (Object obj : ((Iterable) n)) {
                newBag = newBag.remove((AxilObject) obj);
            }
            return newBag.immute();
        } else {
            return remove(n).immute();
        }
	}

	/**
	 * Get the size of this collection. For a list, the size is computed each
	 * time it is requested, so the operation is not constant time as one might
	 * expect.
	 */
	public int size() {
		if (empty()) {
			return 0;
		}
		int size = 0;
		Bag<T> cell = this;
		while(cell != null) {
			size ++;
			cell = cell.next;
		}
		return size;
	}


	/**
	 * Tell if this collection is empty. Use of this method is much preferred
	 * over the idiom 'size() == 0' since determination of size may not be a
	 * constant time operation.
	 */
	public final boolean empty() {
		return this.object == null;
	}

    /**
     * Mark this object as immutable, preventing any further changes. Any
     * attempt to alter this collection after this point results in an exception.
     */
    public Bag<T> immute() {
        immutable = true;
        return this;
    }

    private void edit() {
        if (immutable) {
            throw error(axil(), "immutable-object");
        }
    }

    /**
     * Created a new bag that does not contain the given object (remove all instances).
     *
     * @return
     * A mutable bag
     *
     * @param dump
     * an object to be removed from the bag
     */
    private Bag<T> remove(AxilObject dump) {
        Bag<T> newHead = dump.equalTo(object) ? next.remove(dump) : cloned(); // Make sure it isn't the first item on the list
        Bag<T> placeHolder = newHead.next;
        Bag<T> newPlaceHolder = newHead;
        while (placeHolder != null) {
            if (placeHolder.object.equalTo(dump)) {
                placeHolder = placeHolder.next;
            } else {
                newPlaceHolder.next = placeHolder;
                newPlaceHolder = newPlaceHolder.next;
                placeHolder = placeHolder.next;
            }
        }
        newPlaceHolder.next = null;
        return newHead;
    }

    /**
     * Clone this object at a sufficiently deep level to avoid damaging it.
     *
     * @return
     * A mutable bag
     */
    private Bag<T> cloned() {
        if (empty()) {
            return new Bag();
        }
        Bag<T> newHead = new Bag<T>(this.object);
        if (this.next.equals(null)) {
            return newHead;
        }
        for (Object obj : this.next) {
            Bag<T> newBag = new Bag((AxilObject) obj);
            newBag.next = newHead.next;
            newHead.next = newBag;
        }
        return newHead;
    }

	static final class Iter<T extends AxilObject> implements Iterator<T> {
		private Bag<T> head;

		Iter(Bag<T> head) {
			this.head = head;
		}

		public boolean hasNext() {
			return head != null;
		}

		public T next() {
			T v = head.object;
			head = head.next;
			return v;
		}

		public void remove() {
            throw error(axil(), "immutable-collection");
		}
	}

	static final class Empty<T> implements Iterator<T> {
		public boolean hasNext() {
			return false;
		}
		public T next()			 {
			return null;
		}
		public void remove() {
            throw error(axil(), "immutable-collection");
		}
	}

	/**
	 * Returns an iterator over a set of elements of type T. The iterator
	 * returned does not allow for alteration of this collection.
	 */
	public Iterator<T> iterator() {
		return empty() ? new Empty<T>() : new Iter<T>(this);
	}
}
